package com.thoughtworks.recruit.test;

import com.thoughtworks.recruit.test.jgraph.interfaces.GraphPath;
import com.thoughtworks.recruit.test.jgraph.path.AllDiGraphPaths;
import com.thoughtworks.recruit.test.jgraph.graph.DefaultDiWeightedGraph;
import com.thoughtworks.recruit.test.jgraph.graph.DefaultWeightedEdge;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.Collectors;

/**
 * The main class to resolve the problem of trains home test, which includes computing the distance of the specified
 * vertices and the shortest path of two vertices.
 *
 */
public final class Trains {

    final static String NO_EDGE = "NO SUCH ROUTE";
    final static Double DEFAULT_WEIGHT = 0D;

    private Trains() {
    }

    /**
     * The starting point for the demo.
     * usage: java -DinputFileName=C:/graph.txt jar thoughtworks-trains-1.0-SNAPSHOT.jar com.thoughtworks.recruit.test.Trains
     *
     * @param args ignored.
     */
    public static void main(String[] args) {

        // mandatory check
        Objects.requireNonNull(System.getProperty("inputFileName"),
                "inputFileName of VM Arguments is missing.");

        final String filePathString = System.getProperty("inputFileName");
        checkGraphInputFile(filePathString);

        final String graphContent = readGraphRawStringFromFile(filePathString);
        printfResult(String.format("Graph: %s", graphContent), null);

        final String[] edgesString = graphContent.split(",");
        final DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph = buildGraph(edgesString);

        printfResult("Expected Output:", null);

        // #1. The distance of the route A-B-C
        Double dis1 = computeDistanceBetweenThreeVertices(graph, "A", "B", "C");
        printfResult(dis1 == DEFAULT_WEIGHT ? NO_EDGE : String.valueOf(dis1.intValue()), 1);

        // #2. The distance of the route A-D.
        Double dis2 = computeDistanceBetweenTwoVertices(graph, "A", "D");
        printfResult(dis2 == DEFAULT_WEIGHT ? NO_EDGE : String.valueOf(dis2.intValue()), 2);

        // #3. The distance of the route A-D-C.
        Double dis3 = computeDistanceBetweenThreeVertices(graph, "A", "D", "C");
        printfResult(dis3 == DEFAULT_WEIGHT ? NO_EDGE : String.valueOf(dis3.intValue()), 3);

        // #4. The distance of the route A-E-B-C-D.
        Double dis4 = computeDistanceBetweenFiveVertices(graph, "A", "E", "B", "C", "D");
        printfResult(dis4 == DEFAULT_WEIGHT ? NO_EDGE : String.valueOf(dis4.intValue()), 4);

        // #5. The distance of the route A-E-D.
        Double dis5 = computeDistanceBetweenThreeVertices(graph, "A", "E", "D");
        printfResult(dis5 == DEFAULT_WEIGHT ? NO_EDGE : String.valueOf(dis5.intValue()), 5);

        // #6. The number of trips starting at C and ending at C with a maximum of 3 stops.
        // In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
        Integer trips6 = computePathBetweenSameVerticesInMaxDepths(graph, "C", 3);
        printfResult(String.valueOf(trips6), 6);

        // #7. The number of trips starting at A and ending at C with exactly 4 stops.  In the sample data below,
        // there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
        // Assumptions: the max depths limits 4
        Integer trips7 = computePathBetweenTwoVerticesInDepths(graph, "A", "C", 4);
        printfResult(String.valueOf(trips7), 7);

        // #8. The length of the shortest route (in terms of distance to travel) from A to C.
        // Assumptions: the max depths limits 4
        Double dis8 = computeShortestDistanceBetweenTwoVerticesInMaxDepths(graph, "A", "C", 4);
        printfResult(String.valueOf(dis8.intValue()), 8);

        // #9. The length of the shortest route (in terms of distance to travel) from B to B.
        // Assumptions: the max depths limits 4
        Double dis9 = computeShortestDistanceBetweenTwoVerticesInMaxDepths(graph, "B", "B", 4);
        printfResult(String.valueOf(dis9.intValue()), 9);

        // #10. The number of different routes from C to C with a distance of less than 30.
        // In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.
        // Assumptions: the max depths limits 9
        Integer trips10 = computePathBetweenTwoVerticesInMaxDistance(graph, "C", "C", 30);
        printfResult(String.valueOf(trips10), 10);

        waitf();
    }

    private static void printfResult(final String result, final Integer seq) {
        if (seq == null) {
            printf(String.format("%s", result));
            return;
        }

        printf(String.format("Output #%s: %s", seq, result));
    }

    private static void printf(final String msg) {
        if (System.out != null) {
            System.out.printf(msg);
            System.out.printf("%n");
        }
    }

    private static void waitf() {
        try {
            System.in.read();
        } catch (Exception ex) {
        }
    }

    private static Double computeDistanceBetweenThreeVertices(DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex1,
                                                              String vertex2, String vertex3) {
        Double defaultWeight = DEFAULT_WEIGHT;

        if (graph == null) return defaultWeight;

        // check vertices
        assertVertex(graph, vertex1);
        assertVertex(graph, vertex2);
        assertVertex(graph, vertex3);

        // check edges
        DefaultWeightedEdge eVertices12 = graph.getEdge(vertex1, vertex2);
        DefaultWeightedEdge eVertices23 = graph.getEdge(vertex2, vertex3);
        if (eVertices12 == null || eVertices23 == null) {
            return defaultWeight;
        }
        defaultWeight = graph.getEdgeWeight(eVertices12) + graph.getEdgeWeight(eVertices23);
        return defaultWeight;
    }

    private static Double computeDistanceBetweenFiveVertices(DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex1,
                                                             String vertex2, String vertex3, String vertex4, String vertex5) {
        Double defaultWeight = DEFAULT_WEIGHT;

        if (graph == null) return defaultWeight;

        // check vertices
        assertVertex(graph, vertex1);
        assertVertex(graph, vertex2);
        assertVertex(graph, vertex3);
        assertVertex(graph, vertex4);
        assertVertex(graph, vertex5);

        // check edges
        DefaultWeightedEdge eVertices12 = graph.getEdge(vertex1, vertex2);
        DefaultWeightedEdge eVertices23 = graph.getEdge(vertex2, vertex3);
        DefaultWeightedEdge eVertices34 = graph.getEdge(vertex3, vertex4);
        DefaultWeightedEdge eVertices45 = graph.getEdge(vertex4, vertex5);
        if (eVertices12 == null || eVertices23 == null || eVertices34 == null || eVertices45 == null) {
            return defaultWeight;
        }
        defaultWeight = graph.getEdgeWeight(eVertices12) + graph.getEdgeWeight(eVertices23) + graph.getEdgeWeight(eVertices34)
                + graph.getEdgeWeight(eVertices45);
        return defaultWeight;
    }

    private static Double computeDistanceBetweenTwoVertices(DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex1,
                                                            String vertex2) {
        Double defaultWeight = DEFAULT_WEIGHT;

        if (graph == null) return defaultWeight;

        // check vertices
        assertVertex(graph, vertex1);
        assertVertex(graph, vertex2);

        // check edges
        DefaultWeightedEdge eVertices12 = graph.getEdge(vertex1, vertex2);
        if (eVertices12 == null) {
            return defaultWeight;
        }
        defaultWeight = graph.getEdgeWeight(eVertices12);
        return defaultWeight;
    }

    private static Integer computePathBetweenSameVerticesInMaxDepths(DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex,
                                                                     int maxDepths) {
        Double pathInt = DEFAULT_WEIGHT;

        if (graph == null) return pathInt.intValue();

        // check vertex
        assertVertex(graph, vertex);

        List<GraphPath<String, DefaultWeightedEdge>> filterPaths = getPaths(graph, vertex, vertex, maxDepths);

        return filterPaths.size();
    }

    private static Integer computePathBetweenTwoVerticesInDepths(DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex1,
                                                                 String vertex2, int depths) {
        Double pathInt = DEFAULT_WEIGHT;

        if (graph == null) return pathInt.intValue();

        // check vertices
        assertVertex(graph, vertex1);
        assertVertex(graph, vertex2);

        List<GraphPath<String, DefaultWeightedEdge>> filterPaths = getPaths(graph, vertex1, vertex2, depths)
                .stream().filter(p -> p.getLength() == depths).collect(Collectors.toList());

        return filterPaths.size();
    }

    private static Integer computePathBetweenTwoVerticesInMaxDistance(DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex1,
                                                                      String vertex2, int maxDistance) {
        Double pathInt = DEFAULT_WEIGHT;

        if (graph == null) return pathInt.intValue();

        // check vertices
        assertVertex(graph, vertex1);
        assertVertex(graph, vertex2);

        List<GraphPath<String, DefaultWeightedEdge>> filterPaths = getPaths(graph, vertex1, vertex2, 9);

        List<GraphPath<String, DefaultWeightedEdge>> matchedPaths = new ArrayList<>();
        Integer pathMatches = 0;
        Double totDistance;
        if (filterPaths.size() != 0) {
            for (GraphPath<String, DefaultWeightedEdge> path : filterPaths) {
                totDistance = DEFAULT_WEIGHT;
                for (DefaultWeightedEdge edge : path.getEdgeList()) {
                    totDistance = totDistance + graph.getEdgeWeight(edge);
                }
                if(totDistance <= maxDistance) {
                    pathMatches = pathMatches + 1;
                    matchedPaths.add(path);
                }
            }
        }

        return pathMatches;
    }

    private static Double computeShortestDistanceBetweenTwoVerticesInMaxDepths
            (DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex1, String vertex2, int maxDepths) {
        Double defaultWeight = DEFAULT_WEIGHT;

        if (graph == null) return defaultWeight;

        // check vertices
        assertVertex(graph, vertex1);
        assertVertex(graph, vertex2);

        List<GraphPath<String, DefaultWeightedEdge>> filterPaths = getPaths(graph, vertex1, vertex2, maxDepths)
                .stream().sorted(Comparator.comparing(p -> p.getWeight())).collect(Collectors.toList());

        Double totDistance = defaultWeight;
        if (filterPaths.size() != 0) {
            for (DefaultWeightedEdge edge : filterPaths.get(0).getEdgeList()) {
                totDistance = totDistance + graph.getEdgeWeight(edge);
            }
        }

        return filterPaths.size() == 0 ? defaultWeight : totDistance;
    }

    private static List<GraphPath<String, DefaultWeightedEdge>> getPaths(DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex1,
                                                                         String vertex2, int maxDepths) {

        if (graph == null) return Collections.emptyList();

        AllDiGraphPaths<String, DefaultWeightedEdge> pathFindingAlg = new AllDiGraphPaths<>(graph);
        List<GraphPath<String, DefaultWeightedEdge>> allPaths = pathFindingAlg.getAllPaths(Collections.singleton(vertex1),
                Collections.singleton(vertex2), false, maxDepths);

        List<GraphPath<String, DefaultWeightedEdge>> filterPaths = allPaths.stream().filter(p -> p.getLength() != 0)
                .collect(Collectors.toList());

        return filterPaths;
    }

    private static Boolean checkGraphInputFile(final String filePathString) {

        final Path filePath = Paths.get(filePathString);
        if (!Files.exists(filePath) || Files.isDirectory(filePath)) {
            throw new IllegalArgumentException("The input file does not exist.");
        }
        return true;
    }

    private static String readGraphRawStringFromFile(final String fileName) {
        try (BufferedReader br = new BufferedReader(new FileReader(fileName))) {

            String sCurrentLine;

            while ((sCurrentLine = br.readLine()) != null) {
                return sCurrentLine;
            }
            return sCurrentLine;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return "";
    }

    private static void assertVertex(DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph, String vertex)
    {
        if (graph == null) {
            throw new IllegalArgumentException("Graph must NOT be null !");
        }

        if (!(graph.containsVertex(vertex))) {
            throw new IllegalArgumentException("Graph must contain the vertex!");
        }
    }

    private static DefaultDiWeightedGraph<String, DefaultWeightedEdge> buildGraph(final String[] edgesString) {
        DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph = new DefaultDiWeightedGraph<>(DefaultWeightedEdge.class);

        if (edgesString == null || edgesString.length == 0) return graph;

        String sourceVertex;
        String targetVertex;
        Double weight;

        for (String edgeString : edgesString) {
            edgeString = edgeString.trim();
            sourceVertex = String.valueOf(edgeString.charAt(0));
            targetVertex = String.valueOf(edgeString.charAt(1));
            weight = Double.valueOf(String.valueOf(edgeString.charAt(2)));

            graph.addVertex(sourceVertex);
            graph.addVertex(targetVertex);
            graph.setEdgeWeight(graph.addEdge(sourceVertex, targetVertex), weight);
        }

        return graph;
    }

    /**
     * Create a mock directed weighted graph based on String vertices.
     *
     * @return a graph based on String objects.
     */
    private static DefaultDiWeightedGraph<String, DefaultWeightedEdge> createStringGraph() {
        DefaultDiWeightedGraph<String, DefaultWeightedEdge> graph = new DefaultDiWeightedGraph<>(DefaultWeightedEdge.class);

        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");

        graph.setEdgeWeight(graph.addEdge("A", "B"), 5.0d);
        graph.setEdgeWeight(graph.addEdge("B", "C"), 4.0d);
        graph.setEdgeWeight(graph.addEdge("C", "D"), 8.0d);
        graph.setEdgeWeight(graph.addEdge("D", "C"), 8.0d);
        graph.setEdgeWeight(graph.addEdge("D", "E"), 6.0d);
        graph.setEdgeWeight(graph.addEdge("A", "D"), 5.0d);
        graph.setEdgeWeight(graph.addEdge("C", "E"), 2.0d);
        graph.setEdgeWeight(graph.addEdge("E", "B"), 3.0d);
        graph.setEdgeWeight(graph.addEdge("A", "E"), 7.0d);

        return graph;
    }


}
